{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make a Special Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生成特殊数字的最少操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>num</code> ，表示一个非负整数。</p>\n",
    "\n",
    "<p>在一次操作中，您可以选择 <code>num</code> 的任意一位数字并将其删除。请注意，如果你删除 <code>num</code> 中的所有数字，则 <code>num</code> 变为 <code>0</code>。</p>\n",
    "\n",
    "<p>返回最少需要多少次操作可以使 <code>num</code> 变成特殊数字。</p>\n",
    "\n",
    "<p>如果整数 <code>x</code> 能被 <code>25</code> 整除，则该整数 <code>x</code> 被认为是特殊数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"2245047\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>删除数字 num[5] 和 num[6] ，得到数字 \"22450\" ，可以被 25 整除。\n",
    "可以证明要使数字变成特殊数字，最少需要删除 2 位数字。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"2908305\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>删除 num[3]、num[4] 和 num[6] ，得到数字 \"2900\" ，可以被 25 整除。\n",
    "可以证明要使数字变成特殊数字，最少需要删除 3 位数字。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"10\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>删除 num[0] ，得到数字 \"0\" ，可以被 25 整除。\n",
    "可以证明要使数字变成特殊数字，最少需要删除 1 位数字。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 100</code></li>\n",
    "\t<li><code>num</code> 仅由数字 <code>'0'</code> 到 <code>'9'</code> 组成</li>\n",
    "\t<li><code>num</code> 不含任何前导零</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-a-special-number](https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-a-special-number](https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"2245047\"', '\"2908305\"', '\"10\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=0\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for num in nums:\n",
    "                    for nx in (x+num,x-num,x^num):\n",
    "                        if nx==goal:return step+1\n",
    "                        if 0<=nx<=1000 and vis[nx]==0:\n",
    "                            vis[nx]=1\n",
    "                            q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        queue = collections.deque()\n",
    "        queue.appendleft(start)\n",
    "        visited = [0] * 1001\n",
    "        visited[start] = 1\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue) # 一次性全进全出，对应同一个step\n",
    "            step += 1\n",
    "            while size > 0:\n",
    "                q = queue.pop()\n",
    "                size -= 1\n",
    "                visited[q] = 1\n",
    "                for n in nums:\n",
    "                    for q_cal in (q + n, q - n, q ^ n):\n",
    "                        if q_cal == goal:\n",
    "                            return step\n",
    "                        if q_cal >= 0 and q_cal <= 1000 and visited[q_cal] != 1:\n",
    "                            queue.appendleft(q_cal)\n",
    "                            visited[q_cal] = 1\n",
    "                \n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=1\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for num in nums:\n",
    "                    for nx in (x+num,x-num,x^num):\n",
    "                        if nx==goal:return step\n",
    "                        if 0<=nx<=1000 and vis[nx]==0:\n",
    "                            vis[nx]=1\n",
    "                            q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque([(start, 0)])\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]\n",
    "\n",
    "        vis = set()\n",
    "        vis.add(start)\n",
    "\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    if not nx in vis and 0 <= nx <=1000:\n",
    "                        q.append((nx, step+1))\n",
    "                        vis.add(nx)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        visited = deque([start])\n",
    "        visited_num = [0]*1001\n",
    "        counter = 0\n",
    "        while visited:\n",
    "            counter += 1\n",
    "            for _ in range(len(visited)):\n",
    "                v = visited.popleft()\n",
    "                for num in nums:\n",
    "                    for y in [v + num, v - num, v ^ num]:\n",
    "                        if y == goal:\n",
    "                            return counter\n",
    "                        if y>1000 or y<0:\n",
    "                            continue\n",
    "                        if visited_num[y]==0:\n",
    "                            visited_num[y]=1\n",
    "                        else:\n",
    "                            continue\n",
    "                        visited.append(y)\n",
    "            # print(visited)\n",
    "        return -1\n",
    "\"\"\"class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        visited = [False for _ in range(1001)]\n",
    "        visited[start] = True\n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for num in nums:\n",
    "                    for y in (x + num, x - num, x ^ num):\n",
    "                        if y == goal:\n",
    "                            return step\n",
    "                        if 0 <= y <= 1000 and visited[y] == False:\n",
    "                            visited[y] = True\n",
    "                            q.append(y)\n",
    "        return -1\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "\n",
    "        ops = [op1, op2, op3]\n",
    "\n",
    "        vis = [False] * 1001\n",
    "\n",
    "        q = deque([(start, 0)])\n",
    "\n",
    "        vis[start] = True\n",
    "\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "\n",
    "                    if 0 <= nx <= 1000 and not vis[nx]:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx,step + 1))\n",
    "\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op_add = lambda x, y: x + y\n",
    "        op_sub = lambda x, y: x - y\n",
    "        op_xor = lambda x, y: x ^ y\n",
    "        ops = [op_add, op_sub, op_xor]\n",
    "        queue = deque([(start, 0)])\n",
    "        visited = [False] * 1001\n",
    "        visited[start] = True\n",
    "        while queue:\n",
    "            header = queue.popleft()\n",
    "            for num in nums:\n",
    "                for op in ops:\n",
    "                    # print(header)\n",
    "                    next_num = op(header[0], num)\n",
    "                    if next_num == goal:\n",
    "                        return header[1] + 1\n",
    "                    if 0 <= next_num <= 1000 and not visited[next_num]:\n",
    "                        queue.append((next_num,header[1]+1))\n",
    "                        visited[next_num]=True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op_add = lambda x, y: x + y\n",
    "        op_sub = lambda x, y: x - y\n",
    "        op_xor = lambda x, y: x ^ y\n",
    "        ops = [op_add, op_sub, op_xor]\n",
    "        queue = deque([(start, 0)])\n",
    "        visited = [False] * 1001\n",
    "        visited[start] = True\n",
    "        while queue:\n",
    "            header = queue.popleft()\n",
    "            for num in nums:\n",
    "                for op in ops:\n",
    "                    next_num = op(header[0], num)\n",
    "                    if next_num == goal:\n",
    "                        return header[1] + 1\n",
    "                    if 0 <= next_num <= 1000 and not visited[next_num]:\n",
    "                        queue.append((next_num,header[1]+1))\n",
    "                        visited[next_num]=True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # 定义运算\n",
    "        ld1 = lambda x, y: x + y\n",
    "        ld2 = lambda x, y: x - y\n",
    "        ld3 = lambda x, y: x ^ y\n",
    "\n",
    "        ld = [ld1, ld2, ld3]\n",
    "\n",
    "        # 防止重新计算，初始化表格记录已经被添加到队列中的数字\n",
    "        use_list = [False] * 1001\n",
    "\n",
    "        # 定义队列\n",
    "        queue = []\n",
    "        # 队列里面放什么东西呢？，数字(运算后的数字)，步数\n",
    "        queue.insert(0, (start, 0))\n",
    "\n",
    "        # 放进去之后定义start为True\n",
    "        use_list[start] = True\n",
    "\n",
    "        while queue:\n",
    "            # 获取队列data\n",
    "            data, step = queue.pop()\n",
    "\n",
    "            # 遍历nums，遍历ld进行运算\n",
    "            for i in range(len(nums)):\n",
    "                for ld_item in ld:\n",
    "                    tmp_numbers = ld_item(data, nums[i])\n",
    "                    # 判断是否满足条件\n",
    "                    if tmp_numbers == goal:\n",
    "                        return step + 1\n",
    "\n",
    "                    # 不满足条件的情况下，需要做下判断，\n",
    "                    # 不能在use_list里面使用过，数字不能超界限\n",
    "                    if 0 <= tmp_numbers <= 1000 and use_list[tmp_numbers] is False:\n",
    "                        use_list[tmp_numbers] = True\n",
    "                        queue.insert(0, (tmp_numbers, step + 1))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=0\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for i in range(n):\n",
    "                    nx=x+nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "                    nx=x-nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "                    nx=x^nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], s: int, t: int) -> int:\n",
    "        q1, q2 = deque([s]), deque([t])\n",
    "        m1, m2 = {s : 0}, {t : 0}\n",
    "\n",
    "        def update(q1, m1, q2, m2, flag):\n",
    "            m = len(q1)\n",
    "            for _ in range(m):\n",
    "                x = q1.popleft()\n",
    "                step = m1[x]\n",
    "                for num in nums:\n",
    "                    # 正向搜索，出队检查\n",
    "                    if flag:\n",
    "                        if x < 0 or x > 1000:\n",
    "                            continue\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx in m2.keys():\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1.keys():\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "                    else:\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx < 0 or nx > 1000:\n",
    "                                continue\n",
    "                            if nx in m2.keys():\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1.keys():\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "            return -1\n",
    "\n",
    "        while q1 and q2:\n",
    "            if len(q1) <= len(q2):\n",
    "                ans = update(q1, m1, q2, m2, True)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "            else:\n",
    "                ans = update(q2, m2, q1, m1, False)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "        \n",
    "        return -1\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        res = 0\n",
    "        visited = [False] * 1001\n",
    "        while len(q) != 0:\n",
    "            res += 1\n",
    "            for i in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                for incur in nums:\n",
    "                    for i in [cur + incur, cur - incur, cur ^ incur]:\n",
    "                        if i == goal:\n",
    "                            return res\n",
    "                        if 0 <= i <= 1000 and not visited[i]:\n",
    "                            visited[i] = True\n",
    "                            q.append(i)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op1 = lambda x,y: x + y\n",
    "        op2 = lambda x,y: x - y\n",
    "        op3 = lambda x,y: x ^ y\n",
    "        op = [op1,op2,op3]\n",
    "        state = [True] * 1001\n",
    "        q = deque([(start, 1)])\n",
    "        while q:\n",
    "            preid, step = q.popleft()\n",
    "            for nu in nums:\n",
    "                for opi in op:\n",
    "                    nx = opi(preid, nu)\n",
    "                    if nx == goal:\n",
    "                        return step\n",
    "                    if 0 <= nx <= 1000 and state[nx]:\n",
    "                        q.append((nx, step+1))\n",
    "                        state[nx] = False\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, n: List[int], s: int, g: int) -> int:\n",
    "        dis = set()\n",
    "        count  = 1\n",
    "        queue = collections.deque([s])\n",
    "        dis.add(s)\n",
    "        while queue:     \n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for i in n:\n",
    "                    for val in [node+i, node-i, node^i]:\n",
    "                        if val == g:\n",
    "                            return count\n",
    "                        else:\n",
    "                            if 0 <= val <= 1000 and val not in dis:\n",
    "                                queue.append(val)\n",
    "                                dis.add(val)\n",
    "            count += 1\n",
    "        return  -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0, start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step, i = q.popleft()\n",
    "            if i == goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i + j, i - j, i ^ j]:\n",
    "                    if tmp == goal:\n",
    "                        return step+1\n",
    "                    if 0 <= tmp <= 1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step + 1, tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        pq = [(0, start)]\n",
    "        visited = {start}\n",
    "        while pq:\n",
    "            t, cur = heappop(pq)\n",
    "            #print(t,cur)\n",
    "            if cur == goal:\n",
    "                return t\n",
    "            #print(pq,visited)\n",
    "            for x in nums:\n",
    "                for y in (cur + x, cur - x, cur ^ x):\n",
    "                    if y not in visited:\n",
    "                        if y==goal:return t+1\n",
    "                        if 0<=y<=1000:\n",
    "                            visited.add(y)\n",
    "                            heappush(pq, (t + 1, y))\n",
    "                    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0,start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step,i = q.popleft()\n",
    "            if i==goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i+j,i-j,i^j]:\n",
    "                    if tmp==goal:\n",
    "                        return step+1\n",
    "                    if 0<=tmp<=1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step+1,tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = deque([(start,0)])\n",
    "        vis = [False]*(1001)\n",
    "        while q:\n",
    "            x,time = q.popleft()\n",
    "            for y in nums:\n",
    "                if x+y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x+y <= 1000 and vis[x+y] == False:\n",
    "                    vis[x+y] = True\n",
    "                    q.append((x+y,time+1))\n",
    "                if x-y == goal:\n",
    "                    return time + 1  \n",
    "                if 0 <= x-y <= 1000 and vis[x-y] == False:\n",
    "                    vis[x-y] = True\n",
    "                    q.append((x-y,time+1))\n",
    "                if x^y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x^y <= 1000 and vis[x^y] == False:\n",
    "                    vis[x^y] = True\n",
    "                    q.append((x^y,time+1))\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums, start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        vst = [0] * 1001\n",
    "        vst[start] = 1\n",
    "        q = deque([(start, 0)])\n",
    "        ops = [lambda x, y: x + y, lambda x, y: x - y, lambda x, y: x ^ y]\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    y = op(x, nums[i])\n",
    "                    if y == goal:\n",
    "                        return step + 1\n",
    "                    if 0 <= y <= 1000 and not vst[y]:\n",
    "                        vst[y] = 1\n",
    "                        q.append((y, step + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [(start,0)]\n",
    "        vis = [False]*(1001)\n",
    "        while q:\n",
    "            x,time = q.pop(0)\n",
    "            for y in nums:\n",
    "                if x+y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x+y <= 1000 and vis[x+y] == False:\n",
    "                    vis[x+y] = True\n",
    "                    q.append((x+y,time+1))\n",
    "                if x-y == goal:\n",
    "                    return time + 1  \n",
    "                if 0 <= x-y <= 1000 and vis[x-y] == False:\n",
    "                    vis[x-y] = True\n",
    "                    q.append((x-y,time+1))\n",
    "                if x^y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x^y <= 1000 and vis[x^y] == False:\n",
    "                    vis[x^y] = True\n",
    "                    q.append((x^y,time+1))\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = {start,}\n",
    "        r = {start,}\n",
    "        ans = 0\n",
    "        x = start\n",
    "        \n",
    "        while q :\n",
    "            r2 = set()\n",
    "            for x in q :\n",
    "                for i in nums :\n",
    "                    t1,t2,t3 = x+i,x- i,x^i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "                    t1 = x -i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "                    t1 = x^i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "            ans +=1            \n",
    "            q=r2.copy()\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        numDict = collections.defaultdict(int)\n",
    "        queue = collections.deque([start])\n",
    "        visited = {start: 0}\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for i in nums:\n",
    "                if goal in (cur + i, cur - i, cur ^ i):\n",
    "                    return visited[cur] + 1\n",
    "                if cur + i not in visited and 0 <= cur + i <= 1000:\n",
    "                    visited[cur + i] = visited[cur] + 1\n",
    "                    queue.append(cur + i)\n",
    "                if cur - i not in visited and 0 <= cur - i <= 1000:\n",
    "                    visited[cur - i] = visited[cur] + 1\n",
    "                    queue.append(cur - i)\n",
    "                if cur ^ i not in visited and 0 <= cur ^ i <= 1000:\n",
    "                    visited[cur ^ i] = visited[cur] + 1\n",
    "                    queue.append(cur ^ i) \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        op = [op1, op2, op3]\n",
    "\n",
    "        state = [False] * 1001\n",
    "        state[start] = True\n",
    "        q = deque([(start, 1)])\n",
    "        while q:\n",
    "            weizhi, step = q.popleft()\n",
    "            for nu in nums:\n",
    "                for i in range(3):\n",
    "                    nx = op[i](weizhi, nu)\n",
    "                    if nx == goal:\n",
    "                        return step\n",
    "                    elif 0<= nx <= 1000 and not state[nx]:\n",
    "                        state[nx] = True\n",
    "                        q.append((nx, step+1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0, start)])\n",
    "        visited = {start, }\n",
    "        \n",
    "        while q:\n",
    "            step, i = q.popleft()\n",
    "            if i == goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i + j, i - j, i ^ j]:\n",
    "                    if tmp == goal:\n",
    "                        return step + 1\n",
    "                    if 0 <= tmp <= 1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step + 1, tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        qu = []\n",
    "        qu.append((start, 0))\n",
    "        vi = [0] * 1001\n",
    "        def bfs():\n",
    "            print(qu)\n",
    "            while len(qu) > 0:\n",
    "                temp = qu.pop(0)\n",
    "                for i in range(len(nums)):\n",
    "                    tempi = temp[0] + nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "                    tempi = temp[0] - nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "                    tempi = temp[0] ^ nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "            return -1\n",
    "        out = bfs()\n",
    "        return out\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q1, q2 = deque([start]), deque([goal])\n",
    "        m1 = {start : 0}\n",
    "        m2 = {goal : 0}\n",
    "\n",
    "        def update(q1, m1, q2, m2, flag):\n",
    "            for _ in range(len(q1)):\n",
    "                x = q1.popleft()\n",
    "                step = m1[x]\n",
    "                for num in nums:\n",
    "                    # 正向\n",
    "                    if flag:\n",
    "                        if x < 0 or x > 1000:\n",
    "                            continue\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx in m2:\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1:\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "                    # 反向看输入\n",
    "                    else:\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx < 0 or nx > 1000:\n",
    "                                continue\n",
    "                            if nx in m2:\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1:\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "        while q1 and q2:\n",
    "            if len(q1) <= len(q2):\n",
    "                ans = update(q1, m1, q2, m2, True)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "            else:\n",
    "                ans = update(q2, m2, q1, m1, False)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0,start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step,i = q.popleft()\n",
    "            if i==goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i+j,i-j,i^j]:\n",
    "                    if tmp==goal:\n",
    "                        return step+1\n",
    "                    if 0<=tmp<=1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step+1,tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "# 创建一个队列\n",
    "queue = Queue()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        a = set()\n",
    "\n",
    "        def bfs(x, ans):\n",
    "            if len(x) == 0:\n",
    "                return -1\n",
    "            ans += 1\n",
    "            tmp = set()\n",
    "            for i in x:\n",
    "                for num in nums:\n",
    "                    if i + num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i + num <= 1000 and (i + num) not in a:\n",
    "                        tmp.add(i + num)\n",
    "                        a.add(i + num)\n",
    "                    if i - num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i - num <= 1000 and (i - num) not in a:\n",
    "                        tmp.add(i - num)\n",
    "                        a.add(i - num)\n",
    "                    if i ^ num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i ^ num <= 1000 and (i ^ num) not in a:\n",
    "                        tmp.add(i ^ num)\n",
    "                        a.add(i ^ num)\n",
    "            return bfs(tmp, ans)\n",
    "\n",
    "        return bfs({start}, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        if start == goal: return 0\n",
    "        visited = set()\n",
    "        queue = deque([start])\n",
    "        res = 0\n",
    "        while len(queue) != 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cn = queue.popleft()\n",
    "                if cn == goal: return res\n",
    "                if cn < 0 or cn > 1000 or cn in visited: continue\n",
    "                visited.add(cn)\n",
    "                for i in nums:\n",
    "                    queue.append(cn + i)\n",
    "                    queue.append(cn - i)\n",
    "                    queue.append(cn ^ i)\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [start]\n",
    "        vis = [False]*(1001)\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000:\n",
    "                    continue\n",
    "                if vis[x]:\n",
    "                    continue\n",
    "                vis[x] = True \n",
    "                for y in nums:\n",
    "                    q.append(x+y)\n",
    "                    q.append(x-y)\n",
    "                    q.append(x^y)\n",
    "            time += 1\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [start]\n",
    "        seen = set()\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000 or x in seen:\n",
    "                    continue\n",
    "                seen.add(x)\n",
    "                for y in nums:\n",
    "                    q.append(x+y)\n",
    "                    q.append(x-y)\n",
    "                    q.append(x^y)\n",
    "            time += 1\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # 目标 start -> goal\n",
    "        # 如果start一直在0 <=start <= 1000范围内那么可以进行任意次操作\n",
    "        q = [start]\n",
    "        seen = set()\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000 or x in seen:\n",
    "                    continue\n",
    "                seen.add(x)\n",
    "                for y in nums:\n",
    "                    q.append(x + y)\n",
    "                    q.append(x - y)\n",
    "                    q.append(x ^ y)\n",
    "            time += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        visit = {start}\n",
    "        \n",
    "        stack = deque([[start, 0]])\n",
    "        while stack:\n",
    "            x, d = stack.popleft()\n",
    "            if x == goal:\n",
    "                return d\n",
    "            if not 0<=x<=1000:\n",
    "                continue\n",
    "            for num in nums:\n",
    "                if x+num not in visit:\n",
    "                    visit.add(x+num)\n",
    "                    stack.append([x+num, d+1])\n",
    "                \n",
    "                if x-num not in visit:\n",
    "                    visit.add(x-num)\n",
    "                    stack.append([x-num, d+1])\n",
    "\n",
    "                if x ^ num not in visit:\n",
    "                    visit.add(x ^ num)\n",
    "                    stack.append([x ^ num, d + 1])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\r\n",
    "        s = set()\r\n",
    "        q = [start]\r\n",
    "        res = 0 \r\n",
    "        while q:\r\n",
    "            tmp = q\r\n",
    "            q = []\r\n",
    "            for x in tmp:\r\n",
    "                if x == goal:\r\n",
    "                    return res \r\n",
    "                if 0 <= x <= 1000:\r\n",
    "                    for y in nums:\r\n",
    "                        if x + y not in s:\r\n",
    "                            s.add(x + y)\r\n",
    "                            q.append(x + y)\r\n",
    "                        if x - y not in s:\r\n",
    "                            s.add(x - y)\r\n",
    "                            q.append(x - y) \r\n",
    "                        if x ^ y not in s:\r\n",
    "                            s.add(x ^ y)\r\n",
    "                            q.append(x ^ y)\r\n",
    "            res += 1\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n=len(nums)\n",
    "        visited=set()\n",
    "\n",
    "        step=-1\n",
    "        q=[start]\n",
    "        visited.add(start)\n",
    "\n",
    "        while q:\n",
    "            step+=1\n",
    "            t=len(q)\n",
    "            for i in range(t):\n",
    "                temp=q[i]\n",
    "                if temp==goal:return step\n",
    "                if temp>1000 or temp<0:continue\n",
    "                for j in nums:\n",
    "                    if temp+j not in visited:\n",
    "                        visited.add(temp+j)\n",
    "                        q.append(temp+j)\n",
    "                    \n",
    "                    if temp-j not in visited:\n",
    "                        visited.add(temp-j)\n",
    "                        q.append(temp-j)\n",
    "\n",
    "                    if temp^j not in visited:\n",
    "                        visited.add(temp^j)\n",
    "                        q.append(temp^j)\n",
    "            q=q[t:]\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        vis.add(start)\n",
    "        q.append([start,0])\n",
    "        while q:\n",
    "            cur,d = q.popleft()\n",
    "            if cur == goal:\n",
    "                return d\n",
    "            if cur > 1000 or cur < 0:\n",
    "                continue\n",
    "            for c in nums:\n",
    "                if cur + c not in vis:\n",
    "                    vis.add(cur + c)\n",
    "                    q.append([cur + c,d + 1])\n",
    "                if cur - c not in vis:\n",
    "                    vis.add(cur - c)\n",
    "                    q.append([cur - c,d + 1])\n",
    "                if cur ^ c not in vis:\n",
    "                    vis.add(cur ^ c)\n",
    "                    q.append([cur ^ c,d + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        if start == goal :\n",
    "            return 0\n",
    "\n",
    "        q = deque([start])\n",
    "        visit = set()\n",
    "        level = 0\n",
    "\n",
    "        while q :\n",
    "            tmp = deque([])\n",
    "            for _ in range(len(q)) :\n",
    "                node = q.popleft()\n",
    "                if node > 1000 or node < 0:\n",
    "                    continue\n",
    "\n",
    "                for num in nums :\n",
    "                    for net in [node + num, node - num, node ^ num] :\n",
    "                        if net == goal :\n",
    "                            return level+1\n",
    "                        if net not in visit :\n",
    "                            visit.add(net)\n",
    "                            tmp.append(net)\n",
    "            q = tmp \n",
    "            level += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n - (\"0\" in num)\n",
    "\n",
    "        def f(s):\n",
    "            i = num.rfind(s[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(s[0] , 0 , i)\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "\n",
    "        return min(ans , f(\"00\") , f(\"25\") , f(\"50\") , f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - (\"0\" in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        ans = len(num) if \"0\" not in num else len(num) - 1\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return len(num)\n",
    "            i = num.rfind(tail[0], 0, i)\n",
    "            if i < 0: return len(num)\n",
    "            return len(num) - i - 2\n",
    "        ans = min(ans, f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num, n = num[::-1], len(num)\n",
    "        def fun(sub):\n",
    "            if (i1 := num.find(sub[1])) == -1: return n\n",
    "            if (i2 := num.find(sub[0],i1 + 1)) == -1: return n\n",
    "            return i2 -1\n",
    "        return min([n-('0' in num)] + [fun(sub) for sub in [\"00\",\"25\",\"50\",\"75\"]]) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n=len(num)\n",
    "        res=n\n",
    "\n",
    "        i=n-1\n",
    "        while i>=0 and num[i]!='0':\n",
    "                i-=1\n",
    "        while i>=0 and num[i]!='5':\n",
    "                i-=1\n",
    "        if i>=0: i+=1\n",
    "        res=min(res,n-1-i)\n",
    "\n",
    "        i=n-1\n",
    "        while i>=0 and num[i]!='5':\n",
    "                i-=1\n",
    "        while i>=0 and num[i]!='2':\n",
    "                i-=1\n",
    "        if i>=0: i+=1\n",
    "        res=min(res,n-1-i)\n",
    "\n",
    "        i=n-1\n",
    "        while i>=0 and num[i]!='5':\n",
    "                i-=1\n",
    "        while i>=0 and num[i]!='7':\n",
    "                i-=1\n",
    "        if i>=0: i+=1\n",
    "        res=min(res,n-1-i)\n",
    "\n",
    "        i=n-1\n",
    "        while i>=0 and num[i]!='0':\n",
    "                i-=1\n",
    "        if i!=-1: i-=1\n",
    "        while i>=0 and num[i]!='0':\n",
    "                i-=1\n",
    "        if i>=0: i+=1\n",
    "        res=min(res,n-1-i)\n",
    "\n",
    "        if '0' in num: res=min(res,n-1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num, n = num[::-1], len(num)\n",
    "        if num.count('0') == 1 and num.count('5') == 0: return n - 1\n",
    "        def f(s, sub):\n",
    "            if (i1 := s.find(sub[1])) == -1: return n\n",
    "            if (i2 := s.find(sub[0], i1 + 1)) == -1: return n \n",
    "            #print(s, sub, i1, i2)\n",
    "            return i2 - 1\n",
    "        return min(f(num, sub) for sub in (\"00\", \"25\", \"50\", \"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        s=len(num)\n",
    "        flag1=False\n",
    "        flag2=False\n",
    "        for i in range(s-1,-1,-1):\n",
    "            if num[i]=='0':\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "                flag1=True\n",
    "            if num[i]=='5':\n",
    "                flag2=True\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "            if flag2 and (num[i] == '2' or num[i]=='7'):\n",
    "                return s-i-2\n",
    "        if not flag1 :\n",
    "            return s\n",
    "        if flag1 :\n",
    "            return s-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        # find()返回目标字符串中匹配的第一个查找字符串的索引\n",
    "        # rfind()返回目标字符串中匹配的最后一个查找字符串的索引\n",
    "        n= len(num)\n",
    "        def index(f):\n",
    "            i=num.rfind(f[1])\n",
    "            if i<0:\n",
    "                return n\n",
    "            i = num.rfind(f[0],0,i)\n",
    "            if i<0:\n",
    "                return n\n",
    "            return n-i-2\n",
    "        return min(n-('0' in num),index('25'),index('75'),index('50'),index('00'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num = list(map(int,num))\n",
    "        c = set()\n",
    "        #找00,25,50,75\n",
    "        for i in range(len(num)-1,-1,-1):\n",
    "            if 0 in c:\n",
    "                if num[i]==0 or num[i]==5: #这里0不用再判断前面有没有其他数是因为num不含前导0\n",
    "                    return len(num)-i-2\n",
    "            if 5 in c:\n",
    "                if num[i]==2 or num[i]==7:\n",
    "                    return len(num)-i-2\n",
    "            c.add(num[i])\n",
    "        \n",
    "        return len(num)-(0 in num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0:return n \n",
    "            i = num.rfind(tail[0], 0, i)\n",
    "            if i < 0:return n \n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f('00'), f('25'), f('50'), f('75'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n\n",
    "        ## 25 75 00 50\n",
    "        valid_suffix_map = {\"5\":[\"2\", \"7\"], \"0\":[\"0\", \"5\"]}\n",
    "        \n",
    "        for k, v in valid_suffix_map.items():\n",
    "            cnt = num.count(k)\n",
    "            if cnt >= 1:\n",
    "                last_appear_idx = num.rindex(k)\n",
    "                remaing_str = num[0:last_appear_idx]\n",
    "                for d in v:\n",
    "                    try:\n",
    "                        last_x_idx = remaing_str.rindex(d)\n",
    "                        if last_x_idx >= 0:\n",
    "                            ans = min(ans, n - (last_x_idx + 2))\n",
    "                    except ValueError:\n",
    "                        pass\n",
    "        \n",
    "        if num.count(\"0\") == 1:\n",
    "            ans = min(ans, n - 1)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        s=len(num)\n",
    "        flag1=False\n",
    "        flag2=False\n",
    "        for i in range(s-1,-1,-1):\n",
    "            if num[i]=='0':\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "                flag1=True\n",
    "            if num[i]=='5':\n",
    "                flag2=True\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "            if flag2 and (num[i] == '2' or num[i]=='7'):\n",
    "                return s-i-2\n",
    "        if not flag1 :\n",
    "            return s\n",
    "        if flag1 :\n",
    "            return s-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0:\n",
    "                return n\n",
    "\n",
    "            i = num.rfind(tail[0], 0, i)\n",
    "            if i < 0:\n",
    "                return n\n",
    "            return n - i - 2\n",
    "\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        if num == '0':\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        def f(tail):\n",
    "            i = n-1\n",
    "            while True:\n",
    "                while i>=0 and num[i]!=tail[-1]:\n",
    "                    i-=1\n",
    "                i-=1\n",
    "                while i>=0 and num[i]!=tail[0]:\n",
    "                    i-=1\n",
    "                break\n",
    "            if i<0:\n",
    "                return n\n",
    "            return n-i-2\n",
    "        return min(n-('0' in num),f('00'),f('25'),f('50'),f('75'))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        return min(self._impl(num, \"00\"), self._impl(num, \"25\"), \\\n",
    "                   self._impl(num, \"50\"), self._impl(num, \"75\"), \\\n",
    "                   len(num) - ('0' in num))\n",
    "\n",
    "    def _impl(self, num: str, tail: str) -> int:\n",
    "        i = num.rfind(tail[1])\n",
    "        if i < 0: return len(num)\n",
    "\n",
    "        i = num.rfind(tail[0], 0, i)\n",
    "        if i < 0: return len(num)\n",
    "\n",
    "        return len(num) - i - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num = list(map(int,num))\n",
    "        c = set()\n",
    "        #找00,25,50,75\n",
    "        for i in range(len(num)-1,-1,-1):\n",
    "            if 0 in c:\n",
    "                if num[i]==0 or num[i]==5: #这里0不用再判断前面有没有其他数是因为num不含前导0\n",
    "                    return len(num)-i-2\n",
    "            if 5 in c:\n",
    "                if num[i]==2 or num[i]==7:\n",
    "                    return len(num)-i-2\n",
    "            c.add(num[i])\n",
    "        \n",
    "        return len(num)-(0 in num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s[::-1]\n",
    "        ans = len([1 for t in s if t != '0'])\n",
    "        p = s.find('0')\n",
    "        if p != -1:\n",
    "            k = s.find('0', p + 1)\n",
    "            if k != -1:\n",
    "                ans = min(ans, k - 1)\n",
    "            k = s.find('5', p + 1)\n",
    "            if k != -1:\n",
    "                ans = min(ans, k - 1)\n",
    "        p = s.find('5')\n",
    "        if p != -1:\n",
    "            k = s.find('2', p + 1)\n",
    "            if k != -1:\n",
    "                ans = min(ans, k - 1)\n",
    "            k = s.find('7', p + 1)\n",
    "            if k != -1:\n",
    "                ans = min(ans, k - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail):\n",
    "            i1 = num.rfind(tail[1])\n",
    "            if i1<0:\n",
    "                return n \n",
    "            i2 = num.rfind(tail[0], 0, i1)\n",
    "            if i2<0:\n",
    "                return n \n",
    "            return n-i2-2\n",
    "        res = min(n-(\"0\" in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        dp = [[n] * 25 for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            x = int(num[i - 1])\n",
    "            for k in range(25):\n",
    "                dp[i][k] = 1 + dp[i - 1][k]\n",
    "            for k in range(25):\n",
    "                dp[i][(k * 10 + x) % 25] = min(dp[i][(k * 10 + x) % 25], dp[i - 1][k])\n",
    "        return dp[n][0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        s=len(num)\n",
    "        flag1=False\n",
    "        flag2=False\n",
    "        for i in range(s-1,-1,-1):\n",
    "            if num[i]=='0':\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "                flag1=True\n",
    "            if num[i]=='5':\n",
    "                flag2=True\n",
    "                if flag1:\n",
    "                    return s-i-2\n",
    "            if flag2 and (num[i] == '2' or num[i]=='7'):\n",
    "                return s-i-2\n",
    "        if not flag1 :\n",
    "            return s\n",
    "        if flag1 :\n",
    "            return s-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(num)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            v = num[i]\n",
    "            if ((v == '0' and cnt['0'] > 0) or (v == '5' and cnt['0'] > 0) or (v == '7' and cnt['5'] > 0) or (v == '2' and cnt['5'] > 0)):\n",
    "                return n-i-2\n",
    "            cnt[v] += 1\n",
    "        return n if cnt['0'] == 0 else n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num):\n",
    "        len_num = len(num)\n",
    "        zero = len_num - 1 if \"0\" in num else len_num\n",
    "        return min(self.f(\"00\", num), self.f(\"25\", num), self.f(\"50\", num), self.f(\"75\", num), zero)\n",
    "\n",
    "    def f(self, target, num):\n",
    "        try:\n",
    "            i = num.rfind(target[1])\n",
    "            if i < 0:\n",
    "                return len(num)\n",
    "            i = num[:i].rfind(target[0])\n",
    "            if i < 0:\n",
    "                return len(num)\n",
    "            return len(num) - i - 2\n",
    "        except IndexError:\n",
    "            return len(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get_l(a:str):\n",
    "            i = num.rfind(a[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(a[0], 0, i)\n",
    "            if i < 0: return n\n",
    "            return n-i-2\n",
    "\n",
    "        return min(n-('0' in num), get_l(\"00\"), get_l(\"25\"), get_l(\"50\"), get_l(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail):\n",
    "            i = num.rfind(tail[1])\n",
    "            if i<0:\n",
    "                return n \n",
    "            i = num[:i].rfind(tail[0])\n",
    "            if i<0:\n",
    "                return n \n",
    "            return n-i-2\n",
    "        # 5种: 0, __00, __25, __50, __75\n",
    "        return min(f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"), n-('0' in num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num = list(map(int,num))\n",
    "        c = set()\n",
    "        #找00,25,50,75\n",
    "        for i in range(len(num)-1,-1,-1):\n",
    "            if 0 in c:\n",
    "                if num[i]==0 or num[i]==5: #这里0不用再判断前面有没有其他数是因为num不含前导0\n",
    "                    return len(num)-i-2\n",
    "            if 5 in c:\n",
    "                if num[i]==2 or num[i]==7:\n",
    "                    return len(num)-i-2\n",
    "            c.add(num[i])\n",
    "        \n",
    "        return len(num)-(0 in num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        dp = [-10**9]*25\n",
    "        dp[0] = 0\n",
    "        for c in num:\n",
    "            g = [-10**9]*25\n",
    "            x  = ord(c)-ord('0')\n",
    "            for j in range(25):\n",
    "                g[j] =  max(g[j],dp[j])\n",
    "                g[(j*10+x)%25] = max(g[(j*10+x)%25],dp[j]+1)\n",
    "            dp = g\n",
    "        print(n,dp[0])\n",
    "        return n-dp[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        num, n = num[::-1], len(num)\n",
    "        def f(sub):\n",
    "            if (i1 := num.find(sub[1])) == -1: return n\n",
    "            if (i2 := num.find(sub[0], i1 + 1)) == -1: return n \n",
    "            return i2 - 1\n",
    "        return min([n - ('0' in num)] + [f(sub) for sub in (\"00\", \"25\", \"50\", \"75\")])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n\n",
    "        if n == 1:\n",
    "            ans = 0 if num == '0' else 1\n",
    "            return ans\n",
    "        \n",
    "        def find_rightmost(s: str, ch: str) -> int:\n",
    "            s = s[::-1]\n",
    "            position = s.find(ch)\n",
    "            if position != -1:\n",
    "                return len(s) - position - 1\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        idx_0 = find_rightmost(num, '0')\n",
    "        if idx_0 > 0:\n",
    "            idx_00 = find_rightmost(num[:idx_0], '0')\n",
    "            if idx_00 == -1:\n",
    "                ans = min(ans, n-1)\n",
    "            else:\n",
    "                #ans = min(ans, n-(idx_0+1)+idx_0-(idx_00+1))\n",
    "                ans = min(ans, n-idx_00-2)\n",
    "\n",
    "            idx_50 = find_rightmost(num[:idx_0], '5')\n",
    "            if idx_50 != -1:\n",
    "                ans = min(ans, n-idx_50-2)\n",
    "\n",
    "        idx_5 = find_rightmost(num, '5')\n",
    "        if idx_5 > 0:\n",
    "            idx_25 = find_rightmost(num[:idx_5], '2')\n",
    "            if idx_25 != -1:\n",
    "                ans = min(ans, n-idx_25-2)\n",
    "            \n",
    "            idx_75 = find_rightmost(num[:idx_5], '7')\n",
    "            if idx_75 != -1:\n",
    "                ans = min(ans, n-idx_75-2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n =  len(num)\n",
    "\n",
    "        def f(tail):\n",
    "            i = num.rfind(tail[1])\n",
    "            if i<0: return n\n",
    "            i = num.rfind(tail[0],0,i)\n",
    "            if i<0: return n\n",
    "            return n-i-2\n",
    "        \n",
    "        return min (n-(\"0\" in num),f(\"00\"),f(\"25\"),f(\"50\"),f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        lon=len(num)\n",
    "        m=lon\n",
    "        i=lon-1\n",
    "        while i>=0:\n",
    "            if num[i]=='0':\n",
    "                i-=1\n",
    "                while i>=0:\n",
    "                    if num[i]=='0' or num[i]=='5':\n",
    "                        m=lon-2-i\n",
    "                        break\n",
    "                    i-=1\n",
    "                else:\n",
    "                    m=lon-1\n",
    "                break\n",
    "            i-=1\n",
    "        \n",
    "        i=lon-1\n",
    "        while i>=0:\n",
    "            if num[i]=='5':\n",
    "                i-=1\n",
    "                while i>=0:\n",
    "                    if num[i]=='2' or num[i]=='7':\n",
    "                        m=min(m,lon-2-i)\n",
    "                        break\n",
    "                    i-=1\n",
    "                break\n",
    "            i-=1\n",
    "        \n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        has5 = False\n",
    "        has0 = False\n",
    "        for r in range(n-1, -1, -1):\n",
    "            if num[r] == '5':\n",
    "                if has0:\n",
    "                    return n - r - 2\n",
    "                has5 = True\n",
    "            elif num[r] == '0':\n",
    "                if has0:\n",
    "                    return n - r - 2\n",
    "                else:\n",
    "                    has0 = True\n",
    "            elif num[r] == '2' or num[r] == '7':\n",
    "                if has5:\n",
    "                    return n - r - 2\n",
    "                \n",
    "        return n-1 if has0 else n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n\n",
    "        if n == 1:\n",
    "            ans = 0 if num == '0' else 1\n",
    "            return ans\n",
    "        \n",
    "        idx_0 = num.rfind('0')\n",
    "        if idx_0 > 0:\n",
    "            idx_00 = num.rfind('0', 0, idx_0)\n",
    "            if idx_00 == -1:\n",
    "                ans = min(ans, n-1)\n",
    "            else:\n",
    "                ans = min(ans, n-idx_00-2)\n",
    "\n",
    "            idx_50 = num.rfind('5', 0, idx_0)\n",
    "            if idx_50 != -1:\n",
    "                ans = min(ans, n-idx_50-2)\n",
    "\n",
    "        idx_5 = num.rfind('5')\n",
    "        if idx_5 > 0:\n",
    "            idx_25 = num.rfind('2', 0, idx_5)\n",
    "            if idx_25 != -1:\n",
    "                ans = min(ans, n-idx_25-2)\n",
    "            \n",
    "            idx_75 = idx_25 = num.rfind('7', 0, idx_5)\n",
    "            if idx_75 != -1:\n",
    "                ans = min(ans, n-idx_75-2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        \"\"\"\n",
    "        if num == '0':\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \"\"\"\n",
    "        def f(tail):\n",
    "            i = n-1\n",
    "            while True:\n",
    "                while i>=0 and num[i]!=tail[-1]:\n",
    "                    i-=1\n",
    "                i-=1\n",
    "                while i>=0 and num[i]!=tail[0]:\n",
    "                    i-=1\n",
    "                break\n",
    "            if i<0:\n",
    "                return n\n",
    "            return n-i-2\n",
    "        return min(n-('0' in num),f('00'),f('25'),f('50'),f('75'))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n\n",
    "        flag5 = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if (flag5==False and num[i]=='5'):\n",
    "                flag5 = True\n",
    "            elif (flag5==True and (num[i]=='2' or num[i]=='7') ):\n",
    "                ans = min(n-i-2, ans)\n",
    "                break\n",
    "        flag0 = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if (flag0==False and num[i]=='0'):\n",
    "                flag0 = True\n",
    "            elif (flag0==True and (num[i]=='0' or num[i]=='5') ):\n",
    "                ans = min(n-i-2, ans)\n",
    "                break\n",
    "        if flag0 == True:\n",
    "            ans = min(ans,n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        flag = False\n",
    "        res = n+1\n",
    "        for j in range(n-1, 0, -1):\n",
    "            if num[j] in ['0', '5']:\n",
    "                for i in range(j-1, -1, -1):\n",
    "                    if num[i]+num[j] in ['00', '25', '50', '75']:\n",
    "                        flag = True\n",
    "                        res = min(res, n-i-2)\n",
    "        if flag:\n",
    "            return res\n",
    "        elif '0' in num:\n",
    "            return n-1\n",
    "        else:\n",
    "            return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        # 后两位25，00，50,75\n",
    "        index = len(num)-1\n",
    "        res = len(num)\n",
    "        cur = 0\n",
    "        # 找 00\n",
    "        cnt = 0\n",
    "        while index >= 0:\n",
    "            if num[index]=='0':\n",
    "                cnt += 1\n",
    "                if cnt==2:\n",
    "                    break\n",
    "            else:\n",
    "                cur += 1\n",
    "            index -= 1\n",
    "\n",
    "        if index>=0:\n",
    "            res = min(res,cur)\n",
    "        elif cnt>0:\n",
    "            res = min(res, cur)\n",
    "\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        # 找25\n",
    "        index = len(num)-1\n",
    "        while index >= 0:\n",
    "            if cnt==0 and num[index]=='5':\n",
    "                cnt += 1\n",
    "            elif cnt==1 and num[index]=='2':\n",
    "                break\n",
    "            else:\n",
    "                cur += 1\n",
    "            index -= 1\n",
    "        \n",
    "        if index>=0:\n",
    "            res = min(res, cur)\n",
    "            \n",
    "        # 找50\n",
    "        cnt=0\n",
    "        cur = 0\n",
    "        index = len(num)-1\n",
    "        while index >= 0:\n",
    "            if cnt==0 and num[index]=='0':\n",
    "                cnt = 1\n",
    "            elif cnt==1 and num[index]=='5':\n",
    "                break\n",
    "            else:\n",
    "                cur += 1\n",
    "            index -= 1\n",
    "\n",
    "        if index>=0:\n",
    "            res = min(res, cur)\n",
    "\n",
    "        # 找75\n",
    "        cur,cnt = 0,0\n",
    "        index = len(num)-1\n",
    "        while index >=0:\n",
    "            if cnt==0 and num[index]=='5':\n",
    "                cnt = 1\n",
    "            elif cnt==1 and num[index]=='7':\n",
    "                break\n",
    "            else:\n",
    "                cur += 1\n",
    "            index -= 1\n",
    "\n",
    "        if index>=0:\n",
    "            res=min(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        lens = 0\n",
    "        pre = False\n",
    "        now = False\n",
    "        dic = {}\n",
    "        for i in range(len(num)-1,-1, -1):\n",
    "            lens += 1\n",
    "            if dic.get('0', -1) == 1 and num[i] in ['0','5']:\n",
    "                now = num[i]\n",
    "                break\n",
    "            elif dic.get('5', -1) == 1 and num[i] in ['2','7']:\n",
    "                now = num[i]\n",
    "                break\n",
    "            if num[i] == '5':\n",
    "                dic[num[i]] = 1\n",
    "                continue\n",
    "            elif num[i] == '0':\n",
    "                dic[num[i]] = 1\n",
    "                continue\n",
    "        print(dic, now)\n",
    "        if dic.get('0', -1) == 1 and not now:\n",
    "            return len(num) - 1\n",
    "        if not now:\n",
    "            return len(num)\n",
    "        if dic and now:\n",
    "            return lens - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        indices = defaultdict(list)\n",
    "\n",
    "        for i, n in enumerate(num):\n",
    "            indices[n].append(i)\n",
    "\n",
    "        answer = len(num)\n",
    "\n",
    "        if len(indices['0']) >= 2:\n",
    "            answer = min(answer, len(num) - 2 - indices['0'][-2])\n",
    "        \n",
    "        if len(indices['0']) >= 1 and len(indices['5']) >= 1:\n",
    "            l = indices['0'][-1]\n",
    "            r = bisect_left(indices['5'], l) - 1\n",
    "            if l > r >= 0:\n",
    "                answer = min(answer, len(num) - 2 - indices['5'][r])\n",
    "        \n",
    "        if len(indices['5']) >= 1:\n",
    "            l = indices['5'][-1]\n",
    "            r = bisect_left(indices['2'], l) - 1\n",
    "            if l > r >= 0:\n",
    "                answer = min(answer, len(num) - 2 - indices['2'][r])\n",
    "            r = bisect_left(indices['7'], l) - 1\n",
    "            if l > r >= 0:\n",
    "                answer = min(answer, len(num) - 2 - indices['7'][r])\n",
    "        \n",
    "        if answer == len(num):\n",
    "            return answer - len(indices['0'])\n",
    "        else:\n",
    "            return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        ans1 = ans2 = ans3 = ans4 = len(num)\n",
    "\n",
    "        # 00\n",
    "        find = 0\n",
    "        for j in range(len(num)-1, -1, -1):\n",
    "            if num[j] == '0' and find == 0:\n",
    "                find +=1\n",
    "            elif num[j] == '0' and find == 1:\n",
    "                ans1 = len(num) - j - 2\n",
    "                break\n",
    "        \n",
    "        find = 0\n",
    "        for j in range(len(num)-1, -1, -1):\n",
    "            if num[j] == '0' and find == 0:\n",
    "                find +=1\n",
    "            elif num[j] == '5' and find == 1:\n",
    "                ans2 = len(num) - j - 2\n",
    "                break\n",
    "        \n",
    "        find = 0\n",
    "        for j in range(len(num)-1, -1, -1):\n",
    "            if num[j] == '5' and find == 0:\n",
    "                find +=1\n",
    "            elif num[j] == '2' and find == 1:\n",
    "                ans3 = len(num) - j - 2\n",
    "                break\n",
    "        \n",
    "        find = 0\n",
    "        for j in range(len(num)-1, -1, -1):\n",
    "            if num[j] == '5' and find == 0:\n",
    "                find +=1\n",
    "            elif num[j] == '7' and find == 1:\n",
    "                ans4 = len(num) - j - 2\n",
    "                break\n",
    "\n",
    "        ans = min(ans1, ans2, ans3, ans4) \n",
    "        if ans == len(num):\n",
    "            for j in range(len(num)-1, -1, -1):\n",
    "                if num[j] == '0':\n",
    "                    ans = len(num) - 1\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        return min(n - ('0' in num), f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail):\n",
    "            i = num.rfind(tail[1])\n",
    "            if i<0:\n",
    "                return n \n",
    "            i = num.rfind(tail[0], 0, i)   # num[:i]中找第一个数\n",
    "            if i<0:\n",
    "                return n \n",
    "            return n-i-2\n",
    "\n",
    "        return min(f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"), n-('0' in num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        a=b=-1\n",
    "        r = len(num)-num.count('0')\n",
    "        for i in range(len(num)-1, -1, -1):\n",
    "            if a == -1:\n",
    "                if num[i] == '0':\n",
    "                    a = i\n",
    "            else:\n",
    "                if num[i] == '0':\n",
    "                    r = min(len(num)-i-2, r)\n",
    "                elif num[i] == '5':\n",
    "                    r = min(len(num)-i-2, r)\n",
    "            if b == -1:\n",
    "                if num[i] == '5':\n",
    "                    b = i\n",
    "            else:\n",
    "                if num[i] == '2':\n",
    "                    r = min(len(num)-i-2, r)\n",
    "                elif num[i] == '7':\n",
    "                    r = min(len(num)-i-2, r)\n",
    "        return r\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        # last two digit is {00, 25, 50, 75}\n",
    "        pre = [-1, -1, -1, -1]  # position of 0, 2, 5, 7\n",
    "        for i in range(len(num))[::-1]:\n",
    "            if num[i] == \"0\":\n",
    "                if pre[0] == -1:\n",
    "                    pre[0] = i\n",
    "                elif pre[0] != -1:\n",
    "                    return len(num) - i - 2\n",
    "            elif num[i] == \"2\":\n",
    "                if pre[2] != -1:\n",
    "                    return len(num) - i - 2\n",
    "            elif num[i] == \"5\":\n",
    "                if pre[0] != -1:\n",
    "                    return len(num) - i - 2\n",
    "                pre[2] = i\n",
    "            elif num[i] == \"7\":\n",
    "                if pre[2] != -1:\n",
    "                    return len(num) - i - 2\n",
    "        return len(num) - num.count(\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n - (\"0\" in num)\n",
    "        def f(tail):\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0:\n",
    "                return inf \n",
    "            i = num[:i].rfind(tail[0])\n",
    "            if i < 0:\n",
    "                return inf \n",
    "            return n-(i+1)-1\n",
    "        return min(ans,f(\"00\"),f(\"25\"),f(\"50\"),f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        # last two digit is {00, 25, 50, 75}\n",
    "        pre = [-1, -1, -1, -1]  # position of 0, 2, 5, 7\n",
    "        for i in range(len(num))[::-1]:\n",
    "            if num[i] == \"0\":\n",
    "                if pre[0] == -1:\n",
    "                    pre[0] = i\n",
    "                elif pre[0] != -1:\n",
    "                    return len(num) - i - 2\n",
    "            elif num[i] == \"2\":\n",
    "                if pre[2] != -1:\n",
    "                    return len(num) - i - 2\n",
    "            elif num[i] == \"5\":\n",
    "                if pre[0] != -1:\n",
    "                    return len(num) - i - 2\n",
    "                pre[2] = i\n",
    "            elif num[i] == \"7\":\n",
    "                if pre[2] != -1:\n",
    "                    return len(num) - i - 2\n",
    "        return len(num) - (\"0\" in num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        cur_n = int(num)\n",
    "        five_cnt = 0\n",
    "        def get_five_end_cnt():\n",
    "            del_cnt = 0\n",
    "            idx = n-1\n",
    "            while idx >= 0:\n",
    "                while idx >= 0 and num[idx] != \"5\":\n",
    "                    del_cnt += 1\n",
    "                    idx -= 1\n",
    "                if idx == -1:\n",
    "                    return del_cnt\n",
    "                idx -= 1\n",
    "                while idx >= 0 and num[idx] not in (\"2\", \"7\"):\n",
    "                    del_cnt += 1\n",
    "                    idx -= 1\n",
    "                if idx == -1:\n",
    "                    del_cnt += 1\n",
    "                return del_cnt\n",
    "\n",
    "        def get_zero_end_cnt():\n",
    "            del_cnt = 0\n",
    "            idx = n-1\n",
    "            while idx >= 0:\n",
    "                while idx >= 0 and num[idx] != \"0\":\n",
    "                    del_cnt += 1\n",
    "                    idx -= 1\n",
    "                if idx == -1:\n",
    "                    return del_cnt\n",
    "                idx -= 1\n",
    "                while idx >= 0 and num[idx] not in (\"0\", \"5\"):\n",
    "                    del_cnt += 1\n",
    "                    idx -= 1\n",
    "                return del_cnt\n",
    "                \n",
    "\n",
    "        five_cnt = get_five_end_cnt()\n",
    "        zero_cnt = get_zero_end_cnt()\n",
    "        return min(five_cnt, zero_cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        suf_arr = ['00', '25', '50', '75']\n",
    "        if len(num) == 1:\n",
    "            return 0 if num == '0' else 1\n",
    "    \n",
    "        if len(num) == 2:\n",
    "            if num in suf_arr:\n",
    "                return 0\n",
    "            elif num[1] == '0':\n",
    "                return 1\n",
    "            \n",
    "        def endWith(suffix: str) -> int:\n",
    "            j, found = len(num) - 1, 0\n",
    "            while j >= 0:\n",
    "                if found == 0:\n",
    "                    if num[j] == suffix[1]:\n",
    "                        found += 1\n",
    "                else:\n",
    "                    # found == 1\n",
    "                    if num[j] == suffix[0]:\n",
    "                        return len(num) - j - 2\n",
    "                j -= 1\n",
    "            return len(num)\n",
    "                    \n",
    "            \n",
    "        \n",
    "        return min(min(endWith(x) for x in suf_arr), len(num) if '0' not in num else len(num) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        ans = n - ('0' in num)\n",
    "        \n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0: return n\n",
    "            i = num[:i].rfind(tail[0], 0, i)\n",
    "            if i < 0: return n\n",
    "            return n - i - 2\n",
    "        \n",
    "        return min(ans, f(\"00\"), f(\"25\"), f(\"50\"), f(\"75\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        count = 0\n",
    "        r_0, r_5 = None, None\n",
    "        for i in reversed(range(len(num))):\n",
    "            if r_0 and r_5:\n",
    "                break\n",
    "            if int(num[i]) == 5 and not r_5:\n",
    "                r_5 = i\n",
    "            elif int(num[i]) == 0 and not r_0:\n",
    "                r_0 = i\n",
    "        if not r_0 and not r_5:\n",
    "            return len(num)\n",
    "        temp_1, temp_2 = None,None\n",
    "        if r_0:\n",
    "            for i in reversed(range(r_0)):\n",
    "                if num[i] == '0' or num[i] == '5':\n",
    "                    temp_1 = r_0 - i - 1 + len(num) - r_0 - 1\n",
    "                    break\n",
    "        if r_5:\n",
    "            for i in reversed(range(r_5)):\n",
    "                if num[i] == '2' or num[i] == '7':\n",
    "                    temp_2 = r_5 - i - 1 + len(num) - r_5 - 1\n",
    "                    break\n",
    "        print(temp_1, temp_2)\n",
    "        if temp_1 is None and temp_2 is None:\n",
    "            if r_0 is None:\n",
    "                return len(num)\n",
    "            else:\n",
    "                return len(num) - 1\n",
    "        elif temp_1 is not None and temp_2 is None:\n",
    "            return temp_1\n",
    "        elif temp_2 is not None and temp_1 is None:\n",
    "            return temp_2\n",
    "        else:\n",
    "            return min(temp_1, temp_2)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        #如果末尾的数为00,25,50,75，那么就可以整除25\n",
    "        loc_2 = []\n",
    "        loc_5 = []\n",
    "        loc_0 = []\n",
    "        loc_7 = []\n",
    "        \n",
    "        for i in range(0, len(num)):\n",
    "            if num[i] == '0':\n",
    "                loc_0.append(i)\n",
    "            if num[i] == '2':\n",
    "                loc_2.append(i)\n",
    "            if num[i] == '5':\n",
    "                loc_5.append(i)\n",
    "            if num[i] == '7':\n",
    "                loc_7.append(i)\n",
    "        \n",
    "        loc_00 = []\n",
    "        loc_25 = []\n",
    "        loc_50 = []\n",
    "        loc_75 = []\n",
    "        \n",
    "        if len(loc_0) >= 2:\n",
    "            loc_00 = [loc_0[-2], loc_0[-1]]\n",
    "        \n",
    "        \n",
    "        if len(loc_5) >= 1:\n",
    "            for i in range(0, len(loc_2)):\n",
    "                if loc_2[-i-1] < loc_5[-1]:\n",
    "                    loc_25 = [loc_2[-i-1], loc_5[-1]]\n",
    "                    break\n",
    "                    \n",
    "        if len(loc_5) >= 1:\n",
    "            for i in range(0, len(loc_7)):\n",
    "                if loc_7[-i-1] < loc_5[-1]:\n",
    "                    loc_75 = [loc_7[-i-1], loc_5[-1]]\n",
    "                    break\n",
    "                    \n",
    "        if len(loc_0) >= 1:\n",
    "            for i in range(0, len(loc_5)):\n",
    "                if loc_5[-i-1] < loc_0[-1]:\n",
    "                    loc_50 = [loc_5[-i-1], loc_0[-1]]\n",
    "                    break\n",
    "        \n",
    "        \n",
    "        del_00 = 90000\n",
    "        del_25 = 90000\n",
    "        del_50 = 90000\n",
    "        del_75 = 90000\n",
    "\n",
    "        if loc_00 != []:\n",
    "            del_00 = (len(num)-1 - loc_00[-1]) + loc_00[-1]-loc_00[0]-1\n",
    "\n",
    "        if loc_25 != []:\n",
    "            del_25 = (len(num)-1 - loc_25[-1]) + loc_25[-1]-loc_25[0]-1\n",
    "\n",
    "        if loc_50 != []:\n",
    "            del_50 = (len(num)-1 - loc_50[-1]) + loc_50[-1]-loc_50[0]-1\n",
    "\n",
    "        if loc_75 != []:\n",
    "            del_75 = (len(num)-1 - loc_75[-1]) + loc_75[-1]-loc_75[0]-1\n",
    "\n",
    "        #print(del_00,del_25,del_50,del_75)\n",
    "\n",
    "        if min(del_00, del_25, del_50, del_75) == 90000:\n",
    "            \n",
    "            if loc_0 != []:\n",
    "                return len(num)-1\n",
    "            else:\n",
    "                return len(num)\n",
    "\n",
    "        else:\n",
    "            return(min(del_00,del_25,del_50,del_75))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        if n == 1:\n",
    "            if num == '0':\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        if n == 2:\n",
    "            if num == '25' or num == '50' or num == '75':\n",
    "                return 0\n",
    "            if num[-1] == '0':\n",
    "                return 1\n",
    "            return 2\n",
    "        \n",
    "        def solve(a, b):\n",
    "            step = 0\n",
    "            i = n-1\n",
    "            while i > 0:\n",
    "                if num[i] != b:\n",
    "                    i -= 1\n",
    "                    step += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            if i == 0:\n",
    "                return n\n",
    "            j = i-1\n",
    "            while j >= 0:\n",
    "                if num[j] != a:\n",
    "                    j -= 1\n",
    "                    step += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            if j == -1:\n",
    "                if '0' in num:\n",
    "                    return n- 1\n",
    "                return n\n",
    "            return step\n",
    "        \n",
    "        ans = min(solve('2', '5'), solve('5', '0'), solve('0', '0'), solve('7', '5'))\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        def f(tail: str) -> int:\n",
    "            i = num.rfind(tail[1])\n",
    "            if i < 0:\n",
    "                return n\n",
    "            i = num.rfind(tail[0], 0, i)\n",
    "            if i < 0:\n",
    "                return n\n",
    "            return n - i - 2\n",
    "        \n",
    "        return min(n - ('0' in num), f('00'), f('25'), f('50'), f('75'))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        if int(num)<25:\n",
    "            if \"0\" in num:\n",
    "                return len(num)-1\n",
    "            else:\n",
    "                return len(num)\n",
    "        ans = 0\n",
    "        if int(num)%25 == 0:\n",
    "            return ans\n",
    "        li = list(num)\n",
    "        #找尾部以0结尾的\n",
    "        temp0 = 0\n",
    "        li0 = li[:]\n",
    "\n",
    "        while li0:\n",
    "            if li0[-1] == \"0\":\n",
    "                break\n",
    "\n",
    "            li0.pop()\n",
    "            temp0 += 1\n",
    "        if li0:\n",
    "            li0.pop()\n",
    "            while li0:\n",
    "                if li0[-1] == \"5\" or li0[-1] == \"0\":\n",
    "                    break\n",
    "                li0.pop()\n",
    "                temp0 += 1\n",
    "        ans = temp0\n",
    "        #找尾部以5结尾的\n",
    "        temp5 = 0\n",
    "        li5 = li[:]\n",
    "        while li5:\n",
    "            if li5[-1] == \"5\":\n",
    "                break\n",
    "\n",
    "            li5.pop()\n",
    "            temp5 += 1\n",
    "        if li5:\n",
    "            li5.pop()\n",
    "            while li5:\n",
    "\n",
    "                if li5[-1] == \"2\" or li5[-1] == \"7\":\n",
    "                    break\n",
    "                li5.pop()\n",
    "                temp5 += 1\n",
    "            else:\n",
    "                temp5 += 1\n",
    "        ans = min(temp5,ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "\n",
    "        numList = [x for x in num]\n",
    "        numLength = len(numList)\n",
    "        minComputation = numLength\n",
    "        zeroIndex1, zeroIndex2, twoIndex, fiveIndex = -1, -1, -1, -1\n",
    "        for i in range(numLength):\n",
    "            index = numLength - 1 - i\n",
    "            if numList[index] == '0':\n",
    "                if zeroIndex1 == -1:\n",
    "                    zeroIndex1 = index\n",
    "                    continue\n",
    "                if zeroIndex2 == -1:\n",
    "                    zeroIndex2 = index\n",
    "                    continue\n",
    "            if numList[index] == '2':\n",
    "                if twoIndex == -1:\n",
    "                    twoIndex = index\n",
    "            if numList[index] == '5':\n",
    "                if fiveIndex == -1:\n",
    "                    fiveIndex = index\n",
    "            \n",
    "        # 50\n",
    "        zeroIndex, fiveIndex = -1, -1\n",
    "        for i in range(numLength):\n",
    "            index = numLength - 1 - i\n",
    "            if numList[index] == '5':\n",
    "                fiveIndex = index\n",
    "                # check the least change\n",
    "                if zeroIndex == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    minComputation = min(minComputation, numLength - fiveIndex - 2)\n",
    "                    break\n",
    "            if numList[index] == '0':\n",
    "                zeroIndex = index\n",
    "                \n",
    "        # 25\n",
    "        twoIndex, fiveIndex = -1, -1\n",
    "        for i in range(numLength):\n",
    "            index = numLength - 1 - i\n",
    "            if numList[index] == '2':\n",
    "                twoIndex = index\n",
    "                # check the least change\n",
    "                if fiveIndex == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    minComputation = min(minComputation, numLength - twoIndex - 2)\n",
    "                    break\n",
    "            if numList[index] == '5':\n",
    "                fiveIndex = index\n",
    "        \n",
    "        \n",
    "        # 75\n",
    "        sevenIndex, fiveIndex = -1, -1\n",
    "        for i in range(numLength):\n",
    "            index = numLength - 1 - i\n",
    "            if numList[index] == '7':\n",
    "                sevenIndex = index\n",
    "                # check the least change\n",
    "                if fiveIndex == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    minComputation = min(minComputation, numLength - sevenIndex - 2)\n",
    "                    break\n",
    "            if numList[index] == '5':\n",
    "                fiveIndex = index        \n",
    "        \n",
    "        # 00\n",
    "        if zeroIndex1 != -1 and zeroIndex2 != -1:\n",
    "            tmp = numLength - zeroIndex2 - 2\n",
    "            minComputation = min(minComputation, tmp)\n",
    "        elif zeroIndex1 != -1 or zeroIndex2 != -1:\n",
    "            minComputation = min(minComputation, numLength - 1)\n",
    "        else:\n",
    "            pass\n",
    "        \n",
    "        return minComputation\n",
    "            \n",
    "        # only one zero or none zero\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        l = list(num)\n",
    "        length = len(l)\n",
    "        ans = length - 1 if '0' in l else length \n",
    "        for i in range(1, length):\n",
    "            if l[i] == '0':\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    if l[j] == '0' or l[j] == '5':\n",
    "                        ans = min(ans, length - j - 2)\n",
    "                        print(length - j - 2, i, l[i], j, l[j])\n",
    "            elif l[i] == '5':\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    if l[j] == '2' or l[j] == '7':\n",
    "                        ans = min(ans, length - j - 2)\n",
    "                        print(length - j - 2, i, l[i], j, l[j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        '''\n",
    "            对于能被25整除的x特点\n",
    "\n",
    "            0,25,50,75,100,125,150,175,200\n",
    "\n",
    "            特点：\n",
    "                末尾为00结尾、25结尾、50结尾、75结尾\n",
    "\n",
    "            例子\n",
    "            ：2908305\n",
    "                i = 5, j = 2,n = 7; n - 1- i, n - 1- i - 1\n",
    "            选择25:5\n",
    "            选择00:3\n",
    "            选择50：无\n",
    "            选择75：无\n",
    "        '''\n",
    "        n = len(num)\n",
    "        \n",
    "        def f(tail):\n",
    "\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                if num[i] == tail[1]:\n",
    "                    break\n",
    "\n",
    "            if i - 1 < 0:\n",
    "                return n\n",
    "\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if num[j] == tail[0]:\n",
    "                    break\n",
    "            print(i, j, tail)\n",
    "            if num[j] != tail[0]:\n",
    "                if num[i] == '0':\n",
    "                    return n - 1\n",
    "                else:\n",
    "                    return n\n",
    "          \n",
    "            return n - j - 2\n",
    "\n",
    "        # if '0' in num:\n",
    "\n",
    "\n",
    "\n",
    "        return min(f('50') , f('25'), f('00'), f('75'))\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.match = ['75', '25', '50', '00']\n",
    "\n",
    "    def delIndex(self, num, index):\n",
    "        return num[:index] + num[index+1:]\n",
    "\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        ans = float('inf')\n",
    "        len_ = len(num)\n",
    "\n",
    "        match_0 = False\n",
    "        match_1 = False\n",
    "        for match in self.match:\n",
    "            copy_num = num\n",
    "            count = 0\n",
    "            len_1 = len(num)\n",
    "            i = len_1 - 1\n",
    "            while i >= 0:\n",
    "                if copy_num[i] == match[1]:\n",
    "                    match_1 = True\n",
    "                    i -= 1\n",
    "                    break\n",
    "                elif copy_num[i] != match[1]:\n",
    "                    count += 1\n",
    "                    copy_num = self.delIndex(copy_num, i)\n",
    "                    if copy_num == '0' and ans == float('inf') and int(num) % 25 != 0:\n",
    "                        ans = min(ans, count)\n",
    "                i -= 1\n",
    "            if not match_1: continue\n",
    "            while i >= 0:\n",
    "                if copy_num[i] == match[0]:\n",
    "                    match_0 = True\n",
    "                    i -= 1\n",
    "                    break\n",
    "                elif copy_num[i] != match[0]:\n",
    "                    count += 1\n",
    "                    copy_num = self.delIndex(copy_num, i)\n",
    "                    if copy_num == '0' and ans == float('inf') and int(num) % 25 != 0:\n",
    "                        ans = min(ans, count)\n",
    "                i -= 1\n",
    "            if match_0:\n",
    "                ans = min(ans, count)\n",
    "        if ans == float('inf'):\n",
    "            return len_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        idx1 = idx2 = -1\n",
    "        for i in range(len(num)-1, -1, -1):\n",
    "            if num[i] == \"0\":\n",
    "                idx1 = max(idx1, i)\n",
    "            elif num[i] == \"5\":\n",
    "                idx2 = max(idx2, i)\n",
    "                \n",
    "        ex1 = ex2 = -1\n",
    "        \n",
    "        for i in range(idx1-1, -1, -1):\n",
    "            if num[i] == \"0\" or num[i] == \"5\":\n",
    "                ex1 = max(ex1, i)\n",
    "                \n",
    "        for i in range(idx2-1, -1, -1):\n",
    "            if num[i] == \"2\" or num[i] == \"7\":\n",
    "                ex2 = max(ex2, i)\n",
    "\n",
    "        print(idx1, idx2)\n",
    "        print(ex1, ex2)\n",
    "        if idx1 == -1:\n",
    "            ans1 = len(num)\n",
    "        elif idx1 != -1 and ex1 == -1:\n",
    "            ans1 = len(num) - 1\n",
    "        elif idx1 != -1 and ex1 != -1:\n",
    "            ans1 = len(num) - ex1 -2\n",
    "            \n",
    "        if idx2 == -1:\n",
    "            ans2 = len(num)\n",
    "        elif idx2 != -1 and ex2 == -1:\n",
    "            ans2 = len(num)\n",
    "        elif idx2 != -1 and ex2 != -1:\n",
    "            ans2 = len(num) - ex2 -2\n",
    "            \n",
    "        return min(ans1, ans2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        #如果末尾的数为00,25,50,75，那么就可以整除25\n",
    "        loc_2 = []\n",
    "        loc_5 = []\n",
    "        loc_0 = []\n",
    "        loc_7 = []\n",
    "        \n",
    "        for i in range(0, len(num)):\n",
    "            if num[i] == '0':\n",
    "                loc_0.append(i)\n",
    "            if num[i] == '2':\n",
    "                loc_2.append(i)\n",
    "            if num[i] == '5':\n",
    "                loc_5.append(i)\n",
    "            if num[i] == '7':\n",
    "                loc_7.append(i)\n",
    "        \n",
    "        loc_00 = []\n",
    "        loc_25 = []\n",
    "        loc_50 = []\n",
    "        loc_75 = []\n",
    "        \n",
    "        if len(loc_0) >= 2:\n",
    "            loc_00 = [loc_0[-2], loc_0[-1]]\n",
    "        \n",
    "        \n",
    "        if len(loc_5) >= 1:\n",
    "            for i in range(0, len(loc_2)):\n",
    "                if loc_2[-i-1] < loc_5[-1]:\n",
    "                    loc_25 = [loc_2[-i-1], loc_5[-1]]\n",
    "                    break\n",
    "                    \n",
    "        if len(loc_5) >= 1:\n",
    "            for i in range(0, len(loc_7)):\n",
    "                if loc_7[-i-1] < loc_5[-1]:\n",
    "                    loc_75 = [loc_7[-i-1], loc_5[-1]]\n",
    "                    break\n",
    "                    \n",
    "        if len(loc_0) >= 1:\n",
    "            for i in range(0, len(loc_5)):\n",
    "                if loc_5[-i-1] < loc_0[-1]:\n",
    "                    loc_50 = [loc_5[-i-1], loc_0[-1]]\n",
    "                    break\n",
    "        \n",
    "        \n",
    "        del_00 = 90000\n",
    "        del_25 = 90000\n",
    "        del_50 = 90000\n",
    "        del_75 = 90000\n",
    "\n",
    "        if loc_00 != []:\n",
    "            del_00 = (len(num)-1 - loc_00[-1]) + loc_00[-1]-loc_00[0]-1\n",
    "\n",
    "        if loc_25 != []:\n",
    "            del_25 = (len(num)-1 - loc_25[-1]) + loc_25[-1]-loc_25[0]-1\n",
    "\n",
    "        if loc_50 != []:\n",
    "            del_50 = (len(num)-1 - loc_50[-1]) + loc_50[-1]-loc_50[0]-1\n",
    "\n",
    "        if loc_75 != []:\n",
    "            del_75 = (len(num)-1 - loc_75[-1]) + loc_75[-1]-loc_75[0]-1\n",
    "\n",
    "        #print(del_00,del_25,del_50,del_75)\n",
    "\n",
    "        if min(del_00, del_25, del_50, del_75) == 90000:\n",
    "            \n",
    "            if loc_0 != []:\n",
    "                return len(num)-1\n",
    "            else:\n",
    "                return len(num)\n",
    "\n",
    "        else:\n",
    "            return(min(del_00,del_25,del_50,del_75))\n",
    "        \n",
    "        \n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        # 00 25 50 75\n",
    "        ans = n # 0肯定可以\n",
    "        d = defaultdict(list)\n",
    "        for i, v in enumerate(num):\n",
    "            d[int(v)].append(i)\n",
    "        # 00\n",
    "        if len(d[0]) >= 2:\n",
    "            x1, x2 = d[0][-2], d[0][-1]\n",
    "            print(1, x1, x2)\n",
    "            print(ans, n, x1, n - 1 - x1 - 1)\n",
    "            ans = min(ans, n - 1 - x2 + x2 - x1 - 1)\n",
    "            print(ans)\n",
    "        # 25\n",
    "        cnt = 0\n",
    "        x2, x5 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 5 and cnt == 0:\n",
    "                x5 = i\n",
    "                cnt = 1\n",
    "            if v == 2 and cnt == 1:\n",
    "                x2 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                print(2, x2, x5)\n",
    "                ans = min(ans, n - 1 - x5 + x5 - x2 - 1)\n",
    "                print(ans)\n",
    "                break\n",
    "        # 50\n",
    "        cnt = 0\n",
    "        x5, x0 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 0 and cnt == 0:\n",
    "                x0 = i\n",
    "                cnt = 1\n",
    "            if v == 5 and cnt == 1:\n",
    "                x5 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                print(3, x5, x0)\n",
    "                ans = min(ans, n - 1 - x0 + x0 - x5 - 1)\n",
    "                break\n",
    " \n",
    "        # 75\n",
    "        cnt = 0\n",
    "        x7, x5 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 5 and cnt == 0:\n",
    "                x5 = i\n",
    "                cnt = 1\n",
    "            if v == 7 and cnt == 1:\n",
    "                x7 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                #print(4, x7, x5)\n",
    "                ans = min(ans, n - 1 - x5 + x5 - x7 - 1)\n",
    "                break\n",
    "        # 纯0\n",
    "        if len(d[0]) > 0:\n",
    "            ans = min(ans, n - len(d[0]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:#0,25,50,75,00,需要倒数第2个0\n",
    "        dc=defaultdict(list)\n",
    "        n=len(num)\n",
    "        for i in range(n):\n",
    "            # if len(dc[num[i]])<2:\n",
    "            dc[num[i]].append(i)\n",
    "            # else:\n",
    "            #     dc[num[i]][-1]=i\n",
    "        res=len(num)-len(dc['0'])\n",
    "        \n",
    "        def delNum(s):#使末尾为s时要删的数量\n",
    "            if len(dc[s[0]])==0 or len(dc[s[1]])==0:\n",
    "                return n\n",
    "            idx=dc[s[1]][-1]\n",
    "            idx=bisect_left(dc[s[0]],idx)\n",
    "            if idx==0:return n\n",
    "            return n-dc[s[0]][idx-1]-2\n",
    "        print(dc)\n",
    "        for s in ['25','50','75','00']:\n",
    "            res=min(res,delNum(s))\n",
    "            # print(s,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        ans = inf\n",
    "        n = len(num)\n",
    "        # 最后的情况 25 50 75 00\n",
    "        indexs = {}\n",
    "        for i, _c in enumerate(num):\n",
    "            if _c in indexs:\n",
    "                indexs[_c].append(i)\n",
    "            else:\n",
    "                indexs[_c] = [i]\n",
    "        print(indexs)\n",
    "\n",
    "        # 枚举四种情况\n",
    "\n",
    "\n",
    "        def situations(first, second):\n",
    "            if first in indexs and second in indexs:\n",
    "                last_second = indexs[second][-1]\n",
    "                valid_first = -1\n",
    "                tmp = indexs[first]\n",
    "                for i in range(len(tmp) - 1, -1, -1):\n",
    "                    if tmp[i] < last_second:\n",
    "                        valid_first = tmp[i]\n",
    "                        break\n",
    "                if valid_first != -1:\n",
    "                    nonlocal ans\n",
    "                    ans = min(ans, n - last_second - 1 + last_second - valid_first - 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        sits = [['2', '5'], ['7','5'], ['5', '0'],['0','0']]\n",
    "        for first, second in sits:\n",
    "            situations(first, second)\n",
    "        # 然后处理特殊情况\n",
    "\n",
    "        # 如果上面都没实现，那怎么办呢？\n",
    "        # 需要看看有没有0\n",
    "        # 删除到只剩0\n",
    "        if '0' in indexs:\n",
    "            ans = min(ans, n - len(indexs['0']))\n",
    "        else:\n",
    "            ans = min(ans, n)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        if int(num) % 25 == 0: return 0\n",
    "        elif len(num) == 1: return 1\n",
    "        elif not \"0\" in num and not \"5\" in num: return len(num)\n",
    "        elif len(num) == 2:\n",
    "            if \"0\" in num: return 1\n",
    "            else : return 2\n",
    "        fives = []\n",
    "        zeros = []\n",
    "        i = len(num) - 1\n",
    "#         for i in range(len(num)):\n",
    "#             if num[i] ==  \"5\": fives.append(i)\n",
    "#             elif num[i] ==  \"0\": zeros.append(i)\n",
    "#         print(fives, zeros)\n",
    "        zeros = []\n",
    "        fives = []\n",
    "        while i >= 0:\n",
    "            if not zeros and num[i] == \"0\":zeros.append(i)\n",
    "            elif len(zeros) == 1:\n",
    "                if num[i] == \"0\" or num[i] == \"5\": zeros.append(i)\n",
    "\n",
    "            if not fives and num[i] == \"5\":fives.append(i)\n",
    "            elif len(fives) == 1:\n",
    "                if num[i] == \"7\" or num[i] == \"2\": fives.append(i)\n",
    "            \n",
    "            i -= 1\n",
    "        result = len(num)\n",
    "        print(fives, zeros)\n",
    "        if len(fives) == 2:\n",
    "            result =  min(result, len(num) - fives[1] - 2)\n",
    "        if len(zeros) == 2:\n",
    "            result =  min(result, len(num) - zeros[1] - 2)\n",
    "        elif len(zeros) == 1:\n",
    "            result = min(result, len(num) -1)\n",
    "        return result\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        if len(num) == 1:\n",
    "            if num[0] =='0':\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        if num[-2:] == '00' or num[-2:] == '25' or num[-2:] == '50' or num[-2:] == '75':\n",
    "            return 0\n",
    "        num1 = list(num)\n",
    "        num2 = list(num)\n",
    "        ans = res = 0\n",
    "        while num1 and num1[-1] != '0':\n",
    "            num1.pop()\n",
    "            ans += 1\n",
    "        while num1:\n",
    "            if len(num1) == 1 or num1[-2] == '0' or num1[-2] == '5':\n",
    "                    break\n",
    "            num1.pop(-2)\n",
    "            ans += 1\n",
    "        while num2 and num2[-1] != '5':\n",
    "            num2.pop()\n",
    "            res += 1\n",
    "        while num2:\n",
    "            if len(num2) == 1:\n",
    "                res += 1\n",
    "                break\n",
    "            if num2[-2] == '2' or num2[-2] == '7':\n",
    "                    break\n",
    "            num2.pop(-2)\n",
    "            res += 1\n",
    "        return min(res, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        if n == 1:\n",
    "            if num == '0':\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        elif n == 2:\n",
    "            if num == '25' or num == '50' or num == '75':\n",
    "                return 0\n",
    "            elif int(num) % 10 == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "        else:\n",
    "            if num[-2:] == '25' or num[-2:] == '50' or num[-2:] == '75' or num[-2:] == '00':\n",
    "                return 0\n",
    "            a = []\n",
    "            b = []\n",
    "            c = []\n",
    "            d = []\n",
    "            for i,x in enumerate(num):\n",
    "                if x == '0':\n",
    "                    a.append(i)\n",
    "                elif x == '2':\n",
    "                    b.append(i)\n",
    "                elif x == '5':\n",
    "                    c.append(i)\n",
    "                elif x == '7':\n",
    "                    d.append(i)\n",
    "            cnt1 = cnt2 = cnt3 = cnt4 = -1\n",
    "            print(a,b,c,d)\n",
    "            if len(a) < 2:\n",
    "                cnt1 = n - len(a)\n",
    "            else:\n",
    "                a1,a2 = a[-1],a[-2]\n",
    "                cnt1 = n - 1 - a1 + (a1 - a2 - 1)\n",
    "            if len(a) < 1:\n",
    "                cnt2 = n\n",
    "            else:\n",
    "                a1 = a[-1]\n",
    "                for c1 in c[::-1]:\n",
    "                    if a1 > c1:\n",
    "                        cnt2 = n - 1 - a1 + (a1 - c1 - 1)\n",
    "                        break\n",
    "                \n",
    "                if cnt2 == -1:\n",
    "                    cnt2 = n - len(a)\n",
    "            \n",
    "            if len(c) == 0:\n",
    "                cnt3 = n - len(a)\n",
    "            else:\n",
    "                c1 = c[-1]\n",
    "                for b1 in b[::-1]:\n",
    "                    if c1 > b1:\n",
    "                        cnt3 = n - 1 - c1 + (c1 - b1 - 1)\n",
    "                        break\n",
    "                if cnt3 == -1:\n",
    "                    cnt3 = n - len(a)\n",
    "            if len(c) == 0:\n",
    "                cnt4 = n - len(a)\n",
    "            else:\n",
    "                c1 = c[-1]\n",
    "                for d1 in d[::-1]:\n",
    "                    if c1 > d1:\n",
    "                        cnt4 = n - 1 - c1 + (c1 - d1 - 1)\n",
    "                        break\n",
    "                if cnt4 == -1:\n",
    "                    cnt4 = n - len(a)\n",
    "            return min([cnt1,cnt2,cnt3,cnt4])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        #末尾两位只可能是25、50、75、00\n",
    "        n=len(num)\n",
    "        ret=inf\n",
    "        for target in ('25','50','75','00'):\n",
    "            i=n-1\n",
    "            t=2\n",
    "            ans=0\n",
    "            has0=0\n",
    "            while t:\n",
    "                if num[i]=='0':\n",
    "                    print(1)\n",
    "                    has0=1\n",
    "                if i<0:\n",
    "                    if has0:\n",
    "                        ans=n-1\n",
    "                    else:\n",
    "                        ans=n\n",
    "                    break\n",
    "                if num[i]==target[t-1]:\n",
    "                    t-=1\n",
    "                else:\n",
    "                    ans+=1\n",
    "                i-=1\n",
    "            ret=min(ret,ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        # 00 25 50 75\n",
    "        ans = n # 0肯定可以\n",
    "        d = defaultdict(list)\n",
    "        for i, v in enumerate(num):\n",
    "            d[int(v)].append(i)\n",
    "        # 00\n",
    "        if len(d[0]) >= 2:\n",
    "            x1, x2 = d[0][-2], d[0][-1]\n",
    "            #print(1, x1, x2)\n",
    "            #print(ans, n, x1, n - 1 - x1 - 1)\n",
    "            ans = min(ans, n - 1 - x2 + x2 - x1 - 1)\n",
    "            #print(ans)\n",
    "        # 25\n",
    "        cnt = 0\n",
    "        x2, x5 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 5 and cnt == 0:\n",
    "                x5 = i\n",
    "                cnt = 1\n",
    "            if v == 2 and cnt == 1:\n",
    "                x2 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                #print(2, x2, x5)\n",
    "                ans = min(ans, n - 1 - x5 + x5 - x2 - 1)\n",
    "                #print(ans)\n",
    "                break\n",
    "        # 50\n",
    "        cnt = 0\n",
    "        x5, x0 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 0 and cnt == 0:\n",
    "                x0 = i\n",
    "                cnt = 1\n",
    "            if v == 5 and cnt == 1:\n",
    "                x5 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                print(3, x5, x0)\n",
    "                ans = min(ans, n - 1 - x0 + x0 - x5 - 1)\n",
    "                break\n",
    " \n",
    "        # 75\n",
    "        cnt = 0\n",
    "        x7, x5 = -1, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = int(num[i])\n",
    "            if v == 5 and cnt == 0:\n",
    "                x5 = i\n",
    "                cnt = 1\n",
    "            if v == 7 and cnt == 1:\n",
    "                x7 = i\n",
    "                cnt = 2\n",
    "            if cnt == 2:\n",
    "                #print(4, x7, x5)\n",
    "                ans = min(ans, n - 1 - x5 + x5 - x7 - 1)\n",
    "                break\n",
    "        # 纯0\n",
    "        if len(d[0]) > 0:\n",
    "            ans = min(ans, n - len(d[0]))\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
